package demo.practice.linklist;

import demo.practice.ListNode;

public class P23_2 {


    public ListNode mergeKLists(ListNode[] lists) {

        ListNode target = null;
        int j = 0;
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] != null) {
                target = lists[i];
                j = i + 1;
                break;
            }
        }

        //把剩下的链表往target上面合
        while (j < lists.length) {
            target = mergeKLists(target, lists[j]);
            j++;
        }

        return target;
    }

    private ListNode mergeKLists(ListNode a, ListNode b) {
        ListNode nroot = new ListNode(0);
        ListNode cur = nroot;

        while (a != null && b != null) {
            if (a.val < b.val) {
                cur.next = a;
                a = a.next;
            } else {
                cur.next = b;
                b = b.next;
            }
            cur = cur.next;
        }
        cur.next = a != null ? a : b;
        return nroot.next;
    }

}
